<?php


set_time_limit(0);
//echo getPostfixValue(evaluatePostfixString('23+'));
//echo recur(array(1, 2, 3));
$minMaxExpression = new MinMaxExpression();
$input = array(2, 1, 3, 4);
echo 'Input:  ' . implode(' ', $input) . '<br>';
//echo $minMaxExpression->getMinExpression($input) . '<br>';
//echo 'Value:  ' . $minMaxExpression->getMinExpressionValue($input) . '<br>';
echo $minMaxExpression->getMaxExpression($input) . '<br>';
echo 'Value:  ' . $minMaxExpression->getMaxExpressionValue($input) . '<br>';

class MinMaxExpression {
	const LEFT_PARENTHESIS = '(';
	const RIGHT_PARENTHESIS = ')';
	
	private $cache = array();
	
	/**
	 * Get MIN expression
	 * 
	 * @param array $input
	 * @return string
	 */
	public function getMinExpression($input) {
		
		$expression = $this->calculateMinExpression($input);
		
		return $this->postfixToInfix($this->postfixExpressionToArray($expression));
	}
	
	public function getMinExpressionValue($input) {
		$expression = $this->calculateMinExpression($input);
		
		return $this->getPostfixValue($this->postfixExpressionToArray($expression));
	}
	/**
	 * Get MAX expression
	 * 
	 * @param array $input
	 * @return string
	 */
	public function getMaxExpression($input) {
		
		$expression = $this->calculateMaxExpression($input);
		
		return $this->postfixToInfix($this->postfixExpressionToArray($expression));
	}
	
	public function getMaxExpressionValue($input) {
		$expression = $this->calculateMaxExpression($input);
		
		return $this->getPostfixValue($this->postfixExpressionToArray($expression));
	}
	/** 
	 * @param array $input
	 * @return string
	 */
	private function calculateMinExpression($input) {
		$size = count($input);
	
		if ($size == 1) {
	
			return $input[0];
		} else {
			$min = 9999999999999;
			$expr = '';
			
			for ($i = 1; $i < $size; $i++) {
				$firstPart = array_slice($input, 0, $i);
				$secondPart = array_slice($input, $i);
				
				$firstKey = implode(',', $firstPart);
				$secondKey = implode(',', $secondPart);
				
				if (isset($this->cache[$firstKey])) {
					//echo $firstKey . '<br>';
					$firstExpression = $this->cache[$firstKey];
				} else {
					$firstExpression = $this->calculateMinExpression($firstPart);
					$this->cache[$firstKey] = $firstExpression;
				}
				
				if (isset($this->cache[$secondKey])) {
					$secondExpression = $this->cache[$secondKey];
				} else {
					$secondExpression = $this->calculateMinExpression($secondPart);
					$this->cache[$secondKey] = $secondExpression;
				}
				
				$newExpression = $firstExpression . $secondExpression;
				
				$potentialMinExpr = $this->getMinPostfixExpression($newExpression . '+', $newExpression . '*');
				$potentialMin = $this->evaluatePostfixExpression($potentialMinExpr);

				if ($min > $potentialMin) {
					$expr = $potentialMinExpr;
					$min = $potentialMin;
				}
			}
			
			return $expr;
		}
	}
	
	/**
	 * @param array $input
	 * @return string
	 */
	private function calculateMaxExpression($input) {
		$size = count($input);
	
		if ($size == 1) {
	
			return $input[0];
		} else {
			$max = 0;
			$expr = '';
			
			for ($i = 1; $i < $size; $i++) {
				$firstPart = array_slice($input, 0, $i);
				$secondPart = array_slice($input, $i);
				
				$firstKey = implode(',', $firstPart);
				$secondKey = implode(',', $secondPart);
				
				if (isset($this->cache[$firstKey])) {
					$firstExpression = $this->cache[$firstKey];
				} else {
					$firstExpression = $this->calculateMaxExpression($firstPart);
					$this->cache[$firstKey] = $firstExpression;
				}
				
				if (isset($this->cache[$secondKey])) {
					$secondExpression = $this->cache[$secondKey];
				} else {
					$secondExpression = $this->calculateMaxExpression($secondPart);
					$this->cache[$secondKey] = $secondExpression;
				}
				
				$newExpression = $firstExpression . $secondExpression;
				
				$potentialMaxExpr = $this->getMaxPostfixExpression($newExpression . '+', $newExpression . '*');
				$potentialMax = $this->evaluatePostfixExpression($potentialMaxExpr);
				
				if ($max < $potentialMax) {
					$expr = $potentialMaxExpr;
					$max = $potentialMax;
				}
			}
			
			return $expr;
		}
	}
	
	/**
	 * Get max postfix expression
	 * 
	 * @param string $a
	 * @param string $b
	 */
	
	private function getMaxPostfixExpression($a, $b) {
		if ($this->evaluatePostfixExpression($a) < $this->evaluatePostfixExpression($b)) {
			
			return $b;
		}
		
		return $a;
	}
	
	/**
	 * Get min postfix expression
	 * 
	 * @param string $a
	 * @param string $b
	 * @return string
	 */
	private function getMinPostfixExpression($a, $b) {
		if ($this->evaluatePostfixExpression($a) < $this->evaluatePostfixExpression($b)) {
			
			return $a;
		}
		
		return $b;
	}
	
	private function evaluatePostfixExpression($string) {
		$postfix = $this->postfixExpressionToArray($string);
	
		return $this->getPostfixValue($postfix);
	}

	/**
	 * @param string $postfix
	 * @return array
	 */
	private function postfixExpressionToArray($postfix) {
		
		return str_split($postfix);
	}
	/**
	 * @param array $postfix
	 * @return integer
	 */
	private function getPostfixValue($postfix) {
		$stack = array();
		$size = count($postfix);
		for ($i = 0; $i < $size; $i++) {
			if (is_numeric($postfix[$i])) {
				array_push($stack, $postfix[$i]);
			} else {
				
				$a = array_pop($stack);
				$b = array_pop($stack);
				
				$result = $a * $b;
				if ($postfix[$i] == '+') {
					$result = $a + $b;
				}
				array_push($stack, $result);
			}
		}
	
		return array_pop($stack);
	}
	
	/**
	 * Infix to postfix expression
	 * 
	 * @param array $expr
	 * @return array
	 */
	private function infixToPostfix($expr) {
		$stack = array();
		$postfix = array();
		$precedentness = array (
			'*' => 1,
			'+' => 2
		);
		
		foreach ($expr as $element) {
			if (is_numeric($element)) {
				array_push($postfix, $element);
			}
			
			if ($element == self::LEFT_PARENTHESIS) {
				array_push($stack, $element);
			}
			
			if ($element == self::RIGHT_PARENTHESIS) {
				while (count($stack) > 0 && end($stack) != self::LEFT_PARENTHESIS) {
					array_push($postfix, array_pop($stack));
				}
				array_pop($stack); 		// Discard the left parenthesis
			}
			
			if (array_key_exists($element, $precedentness)) {
				if (count($stack) == 0 || end($stack) == self::LEFT_PARENTHESIS) {
					array_push($stack, $element);
				} else {
					while (
						count($stack) != 0 &&
						end($stack) != self::LEFT_PARENTHESIS && 
						$precedentness[$element] < $precedentness[end($stack)]
					) {
						array_push($postfix, array_pop($stack));
					}
					array_push($stack, $element);
				}
				
			}
		}
		
		while (count($stack) != 0) {
			array_push($postfix, array_pop($stack));
		}
		
		return $postfix;
	}
	
	/**
	 * Postfix to infix expression
	 * 
	 * @param array $postfix
	 * @return array
	 */
	private function postfixToInfix($postfix) {
		$stack = array();
	
		foreach ($postfix as $symbol) {
			
			if (is_numeric($symbol)) {
				array_push($stack, $symbol);
			} else {
				
				if (count($stack) < 2) {
					echo 'Less than two operands in the stack';
					exit();
				} else {
					$a = array_pop($stack);
					$b = array_pop($stack);
					array_push($stack, '(' . $a . $symbol . $b . ')');
				}
			}
		}
		
		return $stack[0];
	}
}


